package 排序算法;

import java.util.PriorityQueue;
import java.util.Random;

public class AscendingSort {
    /**
     * 冒泡排序
     */
    public int[] bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) { // 比较的趟数  每一趟确定一个最大的数
            int check = 0;
            for (int j = 0; j < n - i - 1; j++) { //还需排序的数
                if (arr[j] > arr[j + 1]) { // 交换
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    check = 1;
                }
            }
            if (check == 0) {// 如 check = 0，说明提前排好顺序了
                break;
            }
        }
        return arr;
    }

    /**
     * 选择排序
     */
    public int[] selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) { //选择的趟数
            int tep = arr[i];
            int index = i;
            for (int j = i + 1; j < n; j++) {
                if(arr[j] < tep) {
                    index = j;
                    tep = arr[j];
                }
            }
            if(index != i) {
                arr[index] = arr[i];
                arr[i] = tep;
            }
        }
        return arr;
    }

    /**
     * 插入排序
     */
    public int[] insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int temp = arr[i];
            int index = i;
            //找到要插入的位置
            for(int j = i; j > 0; j--) {
                if(arr[j - 1] < temp) {
                    break;
                }
                index--;
            }
            //后移，腾出位置
            for(int j = i; j > index;j--){
                arr[j] = arr[j-1];
            }
            // 插入
            arr[index] = temp;
        }

        return arr;
    }

    public int[] insertionSort1(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int tep = arr[i];
            for(int j = i; j > 0; j--) {
                if(tep >= arr[j-1]) {
                    arr[j] = tep;      // 插入
                    break;
                }else {
                    arr[j] = arr[j-1]; //后移
                }
            }
            if(tep < arr[0]) arr[0] = tep;  // 0 位置特殊处理
        }
        return arr;
    }

    /**
     * 希尔排序
     * 对于希尔排序我更喜欢称它为：分组排序，组内插入排序
     */
    public int[] shellSort(int[] arr) {
        int n = arr.length;
        int interval = n;       //  间隔 等于 分组数
        int stand = 2;
        do {
            interval = interval / stand;
            for (int i = 0; i < interval;i++){// 分组
                for (int j = i + interval;j < n;j += interval){ //组内排序
                    // 组内插入排序
                    int tep = arr[j];
                    for (int k = j;k - interval >= 0;k -= interval){
                        if(arr[k - interval] < tep){
                            arr[k] = tep;               // 插入
                            break;
                        }else{
                            arr[k] = arr[k - interval]; // 后移
                        }
                    }
                    if(tep < arr[i]) arr[i] = tep;      // 每组第一个位置特殊处理
                }
            }
        }while (interval > 1);
        return arr;
    }

    /**
     *  堆排序
     */
    public int[] heapSort(int[] arr) {
        int n = arr.length;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            pq.offer(arr[i]);
        }
        for (int i = 0; i < n; i++) {
            arr[i] = pq.poll();
        }
        return arr;
    }


    /**
     * 归并排序
     * 准确的说是：二路归并
     */
    // 递归版
    public int[] mergeSort(int[] arr) {
        int n = arr.length;
        mSort(0,n-1,arr);
        return arr;
    }

    private void mSort(int l, int r, int[] arr) {
        // 归
        if(l >= r) return;


        int mid = (l+r)/2;
        mSort(l,mid,arr);
        mSort(mid+1,r,arr);
        merge(l,mid,r,arr);
    }

    private void merge(int l, int mid, int r, int[] arr) {
        //归
        int[] array = new int[r-l+1];
        int index = 0;
        int i = l,j = mid + 1;
        for(;i <= mid && j <= r;){
            if(arr[i] < arr[j]){
                array[index++] = arr[i++];
            }else {
                array[index++] = arr[j++];
            }
        }
        for(;i <= mid;i++){
            array[index++] = arr[i];
        }
        for(;j <= r;j++){
            array[index++] = arr[j];
        }

        for (int ii = 0; ii < array.length; ii++ ) {
            arr[l++] = array[ii];
        }
    }


    // 非递归版
    public int[] mergeSort1(int[] arr) {
        int n = arr.length;
        return arr;
    }



    /**
     * 快速排序
     * 三数取中版
     */
    //TODO 第一版
//    public int[] quickSort(int[] arr) {
//        int n = arr.length - 1;
//        qSort(0,n,arr);
//        return arr;
//    }
//
//    private void qSort(int l, int r, int[] arr) {
//        if(l >= r) return;
//
//        int mid = l + (r - l) / 2;
//        int standardIndex = findMiddle(l,mid,r,arr);
//        int standard = arr[standardIndex];
//
//        swap(r,standardIndex,arr);
//
//        int i = l,k = r;
//        while(i < k){
//            while (i < k && arr[i] < standard){
//                i++;
//            }
//            while (i < k && arr[k] >= standard){
//                k--;
//            }
//            swap(i,k,arr);
//        }
//
//        swap(i,r,arr);
//        qSort(l,i - 1,arr);
//        qSort(i + 1,r,arr);
//    }
//
//    private void swap(int l, int mid, int[] arr) {
//        int tep = arr[l];
//        arr[l] = arr[mid];
//        arr[mid] = tep;
//    }
//
//    private int findMiddle(int l, int mid, int r, int[] arr) {
//        if(arr[l] >= arr[r]){
//            if (arr[mid] > arr[l]) return l;
//            if(arr[r] > arr[mid]) return r;
//
//            return mid;
//        }else {// r > l
//            if(arr[mid] > arr[r]) return r;
//            if(arr[l] >= arr[mid]) return l;
//
//            return mid;
//        }
//    }

//    //TODO 第二版
//    public int[] quickSort(int[] arr) {
//        int n = arr.length - 1;
//        qSort(0,n,arr);
//        return arr;
//    }
//
//    private void qSort(int l, int r, int[] arr) {
//        if(l >= r) return;
//
//        int mid = l + (r - l) / 2;
//        int standardIndex = findMiddle(l,mid,r,arr);
//        int standard = arr[standardIndex];
//
//        swap(r,standardIndex,arr);
//
//        int i = l,k = r;
//        while(i < k){
//            while (i < k && arr[i] < standard){
//                i++;
//            }
//            while (i < k && arr[k] >= standard){
//                k--;
//            }
//            swap(i,k,arr);
//        }
//
//        swap(i,r,arr);
//        qSort(l,i - 1,arr);
//        qSort(i + 1,r,arr);
//    }
//
//    private void swap(int l, int mid, int[] arr) {
//        int tep = arr[l];
//        arr[l] = arr[mid];
//        arr[mid] = tep;
//    }
//
//    private int findMiddle(int l, int mid, int r, int[] arr) {
//        if((arr[l] - arr[mid]) * (arr[l] - arr[r]) <= 0) return l;
//        if((arr[mid] - arr[l]) * (arr[mid] - arr[r]) <= 0) return mid;
//
//        return r;
//    }

    //TODO： 第三版
    /**
     *  对于快速排序中：挖坑法、前后指针法、左右指针法  使用 三数取中，达到一定的优化
     *  但仍然多多少少还有一些瑕疵， 1，2，6，8，5，5，5，5，5，5，1，1，1
     *  向这些有重复的，便会多次的被排序
     *  三路划分 （效率最高）
     */
    public int[] quickSort(int[] arr) {
        int n = arr.length - 1;
        qSort(0,n,arr);
        return arr;
    }

    private void qSort(int l, int r, int[] arr) {
        if(l >= r) return;
        int standard = arr[l + new Random().nextInt(r - l + 1)];
        int left = l - 1;
        int right = r + 1;
        for (int i = l; i < right; ) {
            if(arr[i] < standard) {
                swap(++left,i++,arr);
            }else if(arr[i] == standard){
                i++;
            }else{
                swap(--right,i,arr);
            }
        }

        qSort(l,left,arr);
        qSort(right,r,arr);
    }

    private void swap(int l, int mid, int[] arr) {
        int tep = arr[l];
        arr[l] = arr[mid];
        arr[mid] = tep;
    }
}
